function Node(data) {
    this.data = data;
    this.next = null;
}

function MyLinkedList() {
    this.head = null;
    this.last = null;
    this.size = 0;
}

MyLinkedList.prototype.insert = function(index, data) {
    if (index < 0 || index > this.size) {
        throw new Error('超出链表节点范围!');
    }
    const insertedNode = new Node(data);
    if (this.size === 0) {
        // 空链表
        this.head = insertedNode;
        this.last = insertedNode;
    } else if (index === 0) {
        // 插入头部
        insertedNode.next = this.head
        this.head = insertedNode
    } else if (index === this.size) {
        // 插到尾部
        this.last.next = insertedNode;
        this.last = insertedNode;
    } else {
        // 插入到中间位置
        const prevNode = this.get(index - 1);
        insertedNode.next = prevNode.next;
        prevNode.next = insertedNode;
    }
    this.size++;
}

MyLinkedList.prototype.remove = function (index) {
    if (index < 0 || index > this.size) {
        throw new Error('超出链表节点范围!')
    }
    let removedNode = null;
    if (index === 0) {
        // 删除头部
        removedNode = this.head;
        this.head = this.head.next;
    } else if (index === this.size - 1) {
        // 删除尾部
        const prevNode = this.get(index - 1)
        removedNode = this.last;
        prevNode.next = null;
        this.last = prevNode;
    } else {
        // 删除中间位置节点
        const prevNode = this.get(index-1);
        const nextNode = prevNode.next.next;
        removedNode = prevNode.next;
        prevNode.next = nextNode;
    }
    this.size--;
    return removedNode;
}

MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index > this.size) {
        throw new Error('超出链表节点范围!')
    }
    const temp = this.head
    for (let i=0; i < index; i++) {
        temp = temp.next;
    }
    return temp;
}

MyLinkedList.prototype.output = function () {
    let temp = this.head;
    while (temp!==null) {
        console.log(temp.data);
        temp = temp.next;
    }
}

const myLinkedList = new MyLinkedList();
myLinkedList.insert(0,3);
myLinkedList.insert(0,4);
myLinkedList.insert(2,9);
myLinkedList.insert(3,5);
myLinkedList.insert(1,6);
myLinkedList.remove(0);
myLinkedList.output();